//class Solution
//{
//public:
//	void hanota(vector<int>& a, vector<int>& b, vector<int>& c)
//	{
//		dfs(a, b, c, a.size());
//	}
//	void dfs(vector<int>& a, vector<int>& b, vector<int>& c, int n)
//	{
//		if (n == 1)
//		{
//			c.push_back(a.back());
//			a.pop_back();
//			return;
//		}
//		dfs(a, c, b, n - 1);
//		c.push_back(a.back());
//			a.pop_back();
//		dfs(b, a, c, n - 1);
//	}
//};



//class Solution
//{
//public:
//	ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)
//	{
//		if (l1 == nullptr) return l2;
//		if (l2 == nullptr) return l1;
//		if (l1->val <= l2->val)
//		{
//			l1->next = mergeTwoLists(l1->next, l2);
//			return l1;
//		}
//		else
//		{
//			l2->next = mergeTwoLists(l1, l2->next);
//			return l2;
//		}
//	}
//};




//class Solution
//{
//public:
//	ListNode* reverseList(ListNode* head)
//	{
//		if (head == nullptr || head->next == nullptr) return head;
//		ListNode* newHead = reverseList(head->next);
//		head->next->next = head;
//		head->next = nullptr;
//		return newHead;
//	}
//};



//class Solution
//{
//public:
//	ListNode* swapPairs(ListNode* head)
//	{
//		if (head == nullptr || head->next == nullptr) return head;
//		auto tmp = swapPairs(head->next->next);
//		auto ret = head->next;
//		head->next->next = head;
//		head->next = tmp;
//		return ret;
//	}
//};


class Solution
{
public:
	double myPow(double x, int n)
	{
		return n < 0 ? 1.0 / pow(x, -(long long)n) : pow(x, n);
	}
	double pow(double x, long long n)
	{
		if (n == 0) return 1.0;
		double tmp = pow(x, n / 2);
		return n % 2 == 0 ? tmp * tmp : tmp * tmp * x;
	}
};